Latency Analysis

PyData Cluj-Napoca, meetup #13, 2020.05.28

Summary

What to look at
How distributions look like
How to measure
How to investigate

- same as last year: programmer, not a data scientist, will try to share some of the things without claiming this is the best way
- not about machine learning, but hopefully you'll learn at least one new trick
- the most important message is to measure things and base your assumptions on facts. Then to know what you are measuring and to be aware of how you are measuring
- background in trading, but applies to any software responding to events
- just like in trading, the simple and common sense measures already capture most of the information, but the conclusion you can draw on limited information are not always right
- most of the time the practice does not match the theory. many projects won't do what they should
- there might be no "recipes" for your case. always look at the data. go with the effort/gains solution that best suits your project

Monitoring

https://play.grafana.org/

Timelines

❌

Timelines

❌

Timelines

✓

Timelines

Histograms

❌

Histograms

❌

Histograms

✓ ?

Histograms

Tivnan et al. - Price Discovery and the Accuracy of Consolidated Data Feeds in the U.S. Equity Markets, Journal of Risk and Financial Management, 2018https://www.mdpi.com/1911-8074/11/4/73/htm

Quantiles plots

Distribution tail plot

✓

Chart by factors

Hasbrouck J., Saar G., Low-latency trading, Journal of Financial Markets, 2013 https://www.erim.eur.nl/fileadmin/erim_content/documents/Saar_Nov6.pdf

Take a step back

What are we measuring?

processing times
roundtrip times

Coordinated omission

Gil Tene - "How NOT to Measure Latency"https://www.youtube.com/watch?v=lJ8ydIuPFeU&t=15m50

- coordinated omission: individual processing time (service time) versus time to completion
- one freeze in this code (GC, I/O freezing, DB lock or reindexing, context switch, interrupt) would be counted only once and it will look good for all instances except one
- if happens outside the timed section, it's not even reported
- time to completion can be biased by a single slow instance as delays add up. queueing: threads or microservices have similar issues
- most monitoring tools are build to show processing time (sometimes called service time) and most performance optimizations and benchmarking done by developers is for the server side, looking only at processing time
- the transport time and waiting time are usually omitted. always measure all parts, including the full rountrip time (or response time)
- when trading you have multiple loops with different distribution chains: there's a roundtrip until you get an acknowledgement from the broker and one till you see the order you placed in market data
- you still need profiling and processing time, but it's not enough. Measure everything

Coordinated omission

- example data in the charts above are from a (pretty dumb) single server that can sustain a throughput of 100 messages per second and has requests from clients at the same rate (100/s)
- the catch is that we have 10 clients sending requests in bursts
- in the top charts we can see how the measurements for processing time and below we see the measurements for the full roundtrips
- we can see how the measurements look way too good for the processing time, while in reality the actual consumer experience is much more painful
- from the shape of the tail you can already tell in which case we are looking at processing times and not at roundtrips, or we have a single consumer and we're way below the throughput rate
- there are delays in the upper chart although i used a 10ms sleep. such delays can have many factors: from cpu overload, to network congestions, synchronization issues or garbage collection to name just a few
- sudden jumps when looking at percentiles usually tell you're dealing with processing times and your measurements might be misleading

Why not averages and few percentiles?

❌

What does the 99th percentile mean?

Whatsapp (2018)

~65 billion messages per day
~500M daily active users
Assuming iid delays and avg # requests per user, 99th percentile slowness will affect (1 - 0.99^(65/0.5)) = 72% of the users

Depending on the number of requests per client:

- certain software can be ok by just looking at the 99th percentile and optimizing that. Or just at averages, but if you've seen this presentation, don't go there
- 95th and 99th percentile are not that rare, assume a trading app placing hundreds of orders per minute
- whatsapp example is biased. Of course the issues are localized and the number of messages for each user is decaying exponentially depending on the user persona, but is an example. Assuming independent samples, the probability of a user experiencing that slowness of over 99th pct is very high
- these delays affecting the users are the roundtrips. By looking only at processing time, you underestimate the impact a lot
- looking at processing time remains very important, but also measure roundtrips and throughput and always be aware what you measure

Grafana dashboard again

Visualize the distribution

- don't look only at few numbers. always check the full distribution, you might find unexpected patterns as in this case
- strange artefacts like in this chart because of the artificial example: client requests made in bursts, 10ms apart, and they all wait for the same resource that takes ~10ms to compute. Useless information in this case, but if you have strange patterns, in your case it might be more relevant
- normally when there are many underlying factors the distribution is smooth
- can have artefacts also due to clocks resolutions, to which we'll get back later
- how distributions usually look like: no simple answer, we will get back to this. processing times versus roundtrip times will obviously be different
- usually both have multiple humps (are multimodal), because multiple factors trigger delays
- usually have an exponentially decaying tail. processing times will have more abrupt decay as the serial correlation is weaker
- only positive numbers (which is always a good thing to check)

Visualize the distribution

Distribution tails

Throughput

- this gets us to throughput: how to diagnose when delays are mainly due to factors specific to your system
- look at roundtrip times and plot the distribution tails
- the same artificial experiment with clients making requests
- sleeps used in the code are a source for the steps at round milliseconds
- compare the distribution tails plots: upper left is the data already seen, 10x the throughput, top right is only 10% above the throughput and below we do not reach that rate
- the 10x Above example looks already really bad starting with the 90th percentile
- difference between charts below the throughput rate should be small and mainly due to random factors
- finding the breaking point: where the chart changes from approximatively linear or convex to concave
- when things start queueing the chart becomes concave, full roundtrip times accumulate. What to do: collapsing requests, spawning new instances for horizontal scaling

Comparing performance

Comparing messaging systems performance

https://bravenewgeek.com/tag/coordinated-omission/

How distributions look like

Example 1: processing times

- in addition to that fit your distribution. The Cullen-Frey chart is useful to put a label to your data. Parametric distributions are "fictions" simplifying the reality. "the map is not the territory" but these simplifications can be useful for predicting probabilities, forecast occurences or identify regime changes. We have a distribution close to gamma in this case
- using here processing times. when using processing times there is serial correlation, but clearly not like for roundtrips
- Square of fitness vs kurtosis chart. Skewness: the 3rd moment of a distribution, a measure of asymmetry of the distribution, kurtosis: the 4th moment of the distribution: not so much about how the peak looks like, but how thin or fat are the tails. A normal distribution will have a value of 3
- can think of distribution moments as the taylor expansion of a function, estimating the distribution better and better
- does not really make sense to go higher than kurtosis, at most to the 5th moment, measuring the asymmetry of the tails, used in finance
- this chart is a useful tool, but it's not a bullet-proof one. It looks only at two shape params. use larger sample sizes, as kurtosis is very sensitive to outliers for small samples
- use bootstrapping when checking distributions or computing numbers: ok for the central tendency or variance. mention random forests as an example of bootstrapping success

How distributions look like

Compare distributions

- looking at a histogram only with the time dimension in log scale
- comparing distributions of processing times before and after release, splitting such that the sample sizes are equal. The red chart is the newer version
- fitting a distribution: just a model
- comparing times versus comparing parametric models: complementary to checking times. Parametric models reduce the complexity to one or two numbers (be it mean and stdev for normal dist and lognorm, rate for exponential, shape and rate for gamma, two shapes for beta)
- all are important. meanlog and mean sd for lognormal, rate and shape for beta. higher decay rate means that fewer latencies have high value, but can also mean that the high latencies are significantly higher
- there is a set of distribution distances you can use to work with numbers rather than gut feeling, but it's not the subject of this talk. To mention: Kullback-Leibler divergence, maximum mean discrepancy, earth mover's distance/Wasserstein used in some GANs and some word embeddings, energy distance/~Cramer, Hellinger/~Bhattacharyya distance

How distributions arise

- let's start with the normal distribution, although we won't find it when modeling delays
- it arises from multiple factors that cancel each other's effect
- generating skewed distributions based on random uniform numbers
- in the natural world the effect of the contributing factors are already a normal distribution, think about how a trait like "how high people can jump" can be attributed to a lot of factors like the body mass, exercise, genes etc., and contributions from each factor are normal distributions on their own
- the normal distribution is the distribution that has the highest entropy from all distributions for a given mean and variance, so it's the most "random" in this class. Departures from it are patterns (and negentropy can be linked to predictability)
- takeout from the crappy animation: no matter the skewness of underlying factors, when many combine, the result will be a normal distribution if they are additive

How distributions arise

- the delays are results of combinations of events or failures. Ex: number of network switches failures. Which resembles the number austro-hungarian soldiers killed by horses
- the modeling of such events can be done using a Poisson distribution
- even if each event happens rarely, the probability of at least one faulty event happening increases when having more and more underlying factors
- think about delays as the result of multiple stages, each stage adding to the latency. Animation: adding a constant delay (in the same scale, for plotting) at each step plus generating a number of events with different probabilities, each event type adding a random uniform delay, that will be multiplicated if multiple events occur. red line: delays, gray line: total number of events
- a simplification, in real life delays can be related. The same factor that triggered a long delay, like a huge packet size, will cause delays in other stages too
- or autocorrelated if system states are not independent. A train that arrives late messes up the schedule for other trains if there's a single available line
- multimodalily if multiple types of events with different distributions can occur
- Poisson process models independent events. Inter-arrival times are exponential random variables. The rate is the event intensity. Poisson has no memory. Non-homogenous Poisson can handle various densities in time, such as the open/close hours. Hawkes process an extension better suited for some real life cases as it handles self-exciting couting, as in trading. Or a message will likely trigger a reply that will trigger another message
- a theoretical model is [again] a fiction, but can help you identify outliers/exceedances/unusual patterns and signal when to scale or predict future loads and scale before you're in troubl. distributions model likelihood of happening for events of underlying processes.
- takeout: the shape of delays distribution will be the result of underlying temporal point processes. multi-modality will be a sign of multiple processes. a truism, but good to be remembered

Examples of distributions

- best fits for delays are usually generalized gamma or lognormal. More rarely beta, as delays are not really bounded
- gamma covers a wide variety of distributions with exponential decay of the tails
- a gamma with shape=1 => exponential. exponential: predict wait time till the 1st event, gamma till the Nth (shape param). if delays are independent, exponential would probably be a good fit
- lognormal: probability distribution with normally distributed log. Normal distribution: the effect is additive, lognormal: the effect is multiplied. Normal: sums of random quantiles, log-normal: products of random quantiles (that comes from the chaining of effects)
- lognormal vs gamma: log of lognormal is symmetric, so not so flexible. Depends on the type of relation, linear or otherwise, between the factor and the delay, then on the number of influences. when there are fewer random factors (or their influence weight is very skewed), it will depart from lognormal
- weibull characteristics: a natural extension of the exponential distribution. theoretically models the "weakest link": time to failure due to first failure in n identical chain links => time to breakdown/first failure can be approximated by weibull
- lognormal and weibull: most popular for modeling skewed dat. Lognormal and Weibull will often be found to model train or plane delays for example. Both have similar shape
- fits not always properly modeling the peak near zero: Weibull handles this better, lognormal has log symmetric

Examples of distributions

- erlang (mention erlang language, rabbitmq): particular of generalized gamma distribution with shape a positive integer. Simultaneous phone calls. In queueing processes the Erlang distribution appears as the distribution of intervals among random events or as the distribution of the queueing time
- gamma distributions with fractional shapes look similar
- gamma distribution of inter-arrival times corresponds to a number of events following a Poisson distribution, both being the result of a Poisson process
- beta distribution works with values between 0 and 1 and is a distribution of probabilities, can have a fit when data normalized in the process
- can still encounter beta when processing time is limited and has few random factors that dwarf other components. beta with alpha = beta = 1 => random uniform
- better for modeling probabilities of having a delay higher than X

Types of distributions

Example 2: roundtrip times, single consumer, localhost, constant small processing time

Types of distributions

Example 3: roundtrip times, single consumer, internet (short distance), constant small processing time

- this is a ping over internet, the main factors is no longer the computer load, but the network delays
- in this case we seem to have a beta distribution, probably because of the simplified experiment and closeness of the server. (normally delays will be better matched by a lognormal/weibull/generalized gamma)
- beta very flexible, can take a lot of shapes, including bell/U/straight lines
- won't speculate on why we have this fit, might be because i had a sleep if 10ms on server side or might be just a fluke, but will mention that: beta models bounded data and is distribution can take quite a lot of forms, has 2 params that control the shape. Also called a posterior distribution, is a conjugate prior of geometric/binomial/bernoulli likelihoods. and suited to model probabilities of on/off outcomes (bernoulli trials)
- usually ping times will be lognormal or Weibull

Types of distributions

Example 4: roundtrip times, single consumer, internet (long distance), no processing time (instant reply)

Types of distributions

Example 5: roundtrip times, single consumer, localhost, heavy server-side calculations based on a random uniform input

How to measure

log everything (if possible)
HdrHistogram
add timestamps to packets and chain them
use high resolution timers (if suitable)
build time series with timestamps, counts, events

- full logs when possible, HdrHistogram for realtime monitoring
- averages easily computed on the fly. stdev can also be computed with an online algo. but averages don't help too much: use a high dynamic range histogram if you can't log everything
- lossy measurements but good enough, similar to a classical histogram with predefined buckets, using a mixture of exponentially increasing and linear bucket value ranges. There is a mantissa and an exponent similarly how float numbers are represented
- add timestamps in the packets you pass around (and chain in/out timestamps)
- you might want to use high resolution timers instead of current time (not always suitable)
- beware that current time can be faulty: date can be changed by user, timezone changes, leap seconds
- if you're running periodic tasks that need accuracy, measure delta time to scheduled time
- create a data frame and sync various monitoring time series to use in analysis later: build a timestamps and events time series, log the times for scheduled tasks, batch runs or any things you know that are running on or can affect the same machines

How to report latencies

- in most of the applications, users see the sum of those times and that's what needs to be optimized
- profiling looks only at processing time, check also network times, look at the full chain in distributed envs
- all measurements are valid, both processing time or roundtrip time. make clear what you measured: processing time, a segment time or a roundtrip. split to as many as you can and it makes sense
- add a histogram and a quantiles or distribution tail plot, whatever you like the most
- reporting mean and stdev alone is meaningless, but you still want them. what stdev means depending on the distribution
- you can use different measures of variance. stdev vs median absolute deviation. biweight midvariance as the "most efficient" (if you want to go that way)… use the measures you know to interpret. use the same measure for multiple experiments
- always report the max, do not drop it. If very off, try to figure it out why
- plot max per unit of time, if you need to estimate a maximum delay, fit a Generalized Extreme Value distribution out of the block maxima
- do not plot just 99.9 99.99 etc., plot a continuum for the full tail. You might not have enough samples to look at the 99.999th percentile

What numbers mean

https://colin-scott.github.io/personal_website/research/interactive_latency.html

Original source: http://norvig.com/21-days.html#answers

What clocks to use

https://www.python.org/dev/peps/pep-0418/

- multiple clocks are available on any server, be aware of their resolution
- when possible use in measurements timestamps from the same computer. System.nanoTime() (Java), time.perf_counter() (python). other measures are affected by clock sync
- can still use time.time() when comparing time from different machines
- or use time.process_time() in python which is more accurate, but reports only computing time! (does not include delays, such as sleep time or when communicating over the network). timeit module uses process_time
- preferably use monotonic timers. System.nanoTime() is monotonic in java
- beware clocks like time.time() are changed by time sync and are not monotonic
- and while time.monotonic() is better, it's updated more rarely, resolution depending on the operating system (and can vary from 1ms be as high as 16ms)
- time() resolution usually close to 200ns

Clock synchronization

measure on the same machine (when possible)
use time synchronization services (NTP, Chrony, etc.)
triangulate different sources
sample times with a ping-like service
account for clock desynchronization

- measure on the same machine (when possible)
- use time synchronization services like NTP, Chrony etc.
- try to triangulate from different sources, check that measurements at each step summed are close to rountrip
- account for clock desynchronization: measure time when sending packet, when receiving and the server time. Difference of local times counts a full roundtrip. Assume symmetrical delays, the central tendency of the difference between remote time and local time (be it average or another measure) should be half a roundtrip
- if you have a chain of servers and not a request/reply where you can add this information, set up a process to sample this difference from time to time (once per minute is enough)
- if no access to run this and sample: we know there is no negative transport time, the median of our one direction transport times should be close to half of ping time rountrip median.

Investigate and improve

"how?": measure
compare distribution tail over time
know your throughput. improve. scale horizontally or collapse when not possible
offline profiling reveals some of the problems, make sure you have enough info also from prod logs
extract critical scenarios from prod logs. stress tests vs historical replays

- the answer to "how" is simpler than expected: measure - measure as many intermediary stages as possible
- find your throughput by looking at processing times, by looking at roundtrips tails shape and by stress testing
- compare the tails for some processing over a rolling window and aim for a (relatively) stable shape of the tails (as in this dumb example with sleeps we looked at)
- once you measured, you almost have the solution in most of the cases. Just like bugs: once reproduced it's almost solved
- offline profiling reveals some of the problems, but not all. add logs such that you can find out sources of delays with what you measured in prod (if possible. sometimes minimizing logging impact => no log)
- write the app able to "parse the logs" => instant replay, mock any level, easy debugging, deploy integration tests instead of unit tests. Easy to say, harder to be done, but the gains will worth it
- test when you reach the throughput and scale when it's reached. trigger alerts, scale horizontally by spawning new instances or other solutions to handle high load (like collapsing)
- run stress tests where you push the limits of things you know might happen, replay historical events as part of a continuous testing process, to make sure you don't have the same failures
- reproduce during testing bursts seen in production. Amplified.

Investigate and improve

your system is not a black box, you can debug it: find the factors that change your latencies
build time series with factors throughout the day
assess their importance
find the dimensions on which delays cluster
prioritize consumer tasks

- try to find patterns or external factors (like a batch high cpu load task in the middle of the day)
- run experiments and compare distributions as well as factors importance
- same as when optimizing isolated code, contribution of factors to latency decays exponentially. most of the time few tweaks will account for most of the performance, the famous 80/20 Pareto principle
- can build a ML model predicting delays and run some variable importance to identify sources. examples: time of day. packet sizes. message types. memory consumption. cpu load
- boosted trees/random forests get a good latency estimator with low effort, accuracy in the "ballpark" of what a studied model would be. You don't really want that (unless you build a simulator and need to model delays), but you can look at variable importance, that reveals the main factors
- not really needed, usually a linear model after normalizing the data (including log or Box-Cox power transform) is good enough
- for example modeling delays in a simulator is good enough with a linear model based on the transaction speed and order placing speed on the inside levels. You can add more signal time series and do seasonal modeling or vector autoregression models but it's a stretch
- check clustering dimensions
- assume 99.9th pct delay ok to happen 1 out of 1000 times for a user, but not that ok to have the same person/region have the problem multiple times in a row
- when routing, prioritize based on your needs, maybe you have some internal tasks that are more critical than others. or treat preferentially consumers that already experienced delays
- process partial data when possible and return results gradually

Investigate and improve

source of delays are stochastic processes, try to identify and understand them
split delays into multiple transport and processing stages
reduce the number of rountrips needed to build a result

https://medium.com/@sachinkagarwal/public-cloud-inter-region-network-latency-as-heat-maps-134e22a5ff19

- source of delays are stochastic processes, they depend on things like the number and size of messages, time of day, news, stock sector. measure conditional delays
- try to fit the underlying process. Looking at event arrivals: might be Poisson process: independent events (emails, notifications etc.), or Hawkes with clustering: reactions on market moves, people looking at news in the morning. Exceedance can be modeled and trigger alerts or start new instances
- there is no recipe, but knowing when and why your performance degrades will help findign solutions
- for full roundtrips with multiple segments: ideally make them independent. Breaking to stages will help you identify problems easier
- look at network, code, size of data transferred or processed. different paths in code or network. beware of asymmetric rountrips due to transferred data sizes
- reduce unnecessary network roundtrips and transfers, compress (being aware of the processing overhead added), process progressively
- heatmap with roundtrip times between your hosts or datacenters. not just averages as in this sample
- correlate log delays from segments or look at excess tail dependence (probability of the observed delayed being in the highest 5/1/0.1% of the tails simultaneously compared with the assumption of independence). Ideally you want components that do not break or hit the limits at the same time
- plot cummulative number of events over multiple days and look for patterns. overlay multiple days

Investigate and improve

target the critical path and historical or theoretical cases of failure
check outliers, major failures may have a chain of things that went wrong
multimodal distributions are a sign of multiple paths, try to identify the split factor
drifts from parametric distributions